#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    unordered_map<int, int> visited;

    vector<int> inDegree;

    vector<int> in;
    vector<vector<int>> to;

    vector<vector<int>> path;
    
    // 成环的边
    vector<vector<int>> cycleEdges;

    // 冲突的边
    vector<vector<int>> conflitEdges;

    unordered_map<string, int> latest;
    
    // 时间复杂度应该是 O(n)
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        if (edges.size() == 0) {
            return {};
        }

        int n = edges.size();

        for (int i = 0; i <= n; i++) {
            visited[i] = 0;

            in.push_back(-1);
            to.push_back({});

            inDegree.push_back(0);
        }

        // 树的基本特性是除根节点外的入度都为 1
        // 因此，如果发现一个节点的入度为 2，
        // 那么两条入边其中一条是需要删除的，
        // 判断标准：删除其中一条边判断是否成环
        for (auto& edge: edges) {
            inDegree[edge[1]]++;

            if (inDegree[edge[1]] == 2) {
                // in 数组用于记录每个节点的入边节点
                conflitEdges.push_back({ in[edge[1]], edge[1] });
                conflitEdges.push_back(edge);
            } else {
                // 这里用了点小技巧，造成冲突的最后一条入边不统计到入边和出边数组
                // 如果此时成环，那么证明需要删除第一条入边
                // 如果此时不成环，那么证明需要删除第二条入边
                in[edge[1]] = edge[0];
                to[edge[0]].push_back(edge[1]);
            }
        }

        // 这里用 dfs 来查找环，其实用并查集更快，但这里特意使用 dfs
        // 将所有的节点作为入口访问，如果节点在上一次深搜中访问过可提前返回
        for (int i = 1; i <= n; i++) {
            dfs(i);
            if (cycleEdges.size() > 0) {
                break;
            }
        }

        // 见上面的描述
        if (conflitEdges.size() > 0) {
            if (cycleEdges.size() > 0) {
                return conflitEdges[0];
            }

            return conflitEdges[1];
        }
        
        for (int i = 0; i < n; i++) {
            latest[to_string(edges[i][0]) + "_" + to_string(edges[i][1])] = i;
        }

        // 如果没有冲突，但是成环，那么找最后出现的边
        if (cycleEdges.size() > 0) {
            return findLatesetEdge(cycleEdges);
        }

        return {};
    }

    // 这里用了比较简单的一种方法，使用边出现的顺序作为边的哈希值
    vector<int> findLatesetEdge(vector<vector<int>>& edges) {
        if (edges.size() == 0) {
            return {};
        }

        vector<int> &latestEdge = edges[0];
        int m = latest[to_string(latestEdge[0]) + "_" + to_string(latestEdge[1])];

        for (auto& edge : edges) {
            int n = latest[to_string(edge[0]) + "_" + to_string(edge[1])];
            if (n > m) {
                latestEdge = edge;
                m = n;
            }
        }

        return latestEdge;
    }

    // 这里使用着色法来进行有向图的 dfs
    void dfs(int i) {
        // 如果状态已经访问过，可提前结束
        if (visited[i] == 2) {
            return;
        }

        // 标记当前的点正在访问
        visited[i] = 1;

        for (auto& n : to[i]) {
            // 提前结束
            if (visited[n] == 2) {
                continue;
            }

            // 记录当前的访问路径
            path.push_back({ i, n });

            // 如果遇到一个正在访问的点，那么证明发现环
            if (visited[n] == 1) {
                // 对路径进行裁剪，只需记录路径中成环的部分路径
                for (int j = path.size() - 1; j >= 0; j--) {
                    if (path[j][0] == n) {
                        break;
                    }
                    cycleEdges.push_back(path[j]);
                }
                return;
            }

            dfs(n);

            // 发现有环，提前结束
            if (cycleEdges.size() > 0) {
                return;
            }

            // 还原路径
            path.pop_back();
        }

        // 当前深搜的路径结束，标记已访问
        visited[i] = 2;
    }
};

int main() {
    vector<vector<int>> edges = {{1,2},{2,3},{3,4},{4,1},{1,5}};

    vector<int> edge = Solution().findRedundantDirectedConnection(edges);

    cout << edge[0] << ", " << edge[1] << endl;

    return 0;
}